import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author 雷明浩
 * @date 2025/7/1 17:27
 */
public class Median {
    // newcoder 数据流中的中位数
    // https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    /**
     * 通过两个优先级队列，将Insert的元素平均存储在两个优先级队列中
     * queue1大根堆存放较小的那半部分
     * queue2小根堆存储较大的那版部分
     * 始终保证queue.size() >= queue.size()
     * 因为还要保证queue1中存储的是较小的半部分，所以在插入之后，还需要判断queue1顶的元素是否大于queue2顶
     * 的元素，如果大于则交换两个队列顶的元素
     */
    PriorityQueue<Integer> queue1 = new PriorityQueue<>(Comparator.reverseOrder());
    PriorityQueue<Integer> queue2 = new PriorityQueue<>();
    public void Insert(Integer num) {
        if (queue1.size() <= queue2.size()) {
            queue1.offer(num);
        } else {
            queue2.offer(num);
        }
        while (!queue1.isEmpty() && !queue2.isEmpty() && queue1.peek() > queue2.peek()) {
            int tmp1 = queue1.poll();
            int tmp2 = queue2.poll();
            queue1.offer(tmp2);
            queue2.offer(tmp1);
        }
    }

    public Double GetMedian() {
        if (queue1.size() == queue2.size()) {
            return (queue1.peek() + queue2.peek()) / 2.0;
        } else {
            return queue1.peek() * 1.0;
        }
    }

    public static void main(String[] args) {
        // 5,2,3,4,1,6,7,0,8
        Median median = new Median();
        median.Insert(5);
        System.out.println(median.GetMedian());
        median.Insert(2);
        System.out.println(median.GetMedian());
        median.Insert(3);
        System.out.println(median.GetMedian());
        median.Insert(4);
        System.out.println(median.GetMedian());
        median.Insert(1);
        System.out.println(median.GetMedian());
        median.Insert(6);
        System.out.println(median.GetMedian());
        median.Insert(7);
        System.out.println(median.GetMedian());
        median.Insert(0);
        System.out.println(median.GetMedian());
        median.Insert(8);
        System.out.println(median.GetMedian());
    }
}